package com.yiwenup.leetcode.daily;

/**
 * https://leetcode-cn.com/problems/rotate-function/
 **/
public class No0396 {
    /**
     * 执行用时：8 ms, 在所有 Java 提交中击败了40.28%的用户
     * 内存消耗：56.4 MB, 在所有 Java 提交中击败了8.60%的用户
     */
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n * 2 + 10];
        for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + nums[(i - 1) % n];
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += nums[i - 1] * (i - 1);
        for (int i = n + 1, cur = ans; i < 2 * n; i++) {
            cur += nums[(i - 1) % n] * (n - 1);
            cur -= sum[i - 1] - sum[i - n];
            if (cur > ans) ans = cur;
        }
        return ans;
    }
}
